//
// B 树
// https://blog.csdn.net/geek_jerome/article/details/78895289
// Created by 麻再挺 on 2021/12/20.
//

#ifndef DATA_STRUCTURE_C_BTREE_H
#define DATA_STRUCTURE_C_BTREE_H

#include <stdio.h>
#include <stdlib.h>
#include "./../constant.h"

// 定义最大阶数
#define MAX_ORDER 10

// 设定 B 树的阶数
const static int bOrder = 4;
// 结点的最大关键字数量
const static int bMax = bOrder - 1;
// 结点的最小关键字数量
const static int bMin = (bOrder - 1) / 2;
// 关键字类型
typedef int BKeyType;

/**
 * B 树存储结构
 * B树和B树结点类型
 */
typedef struct BTNode {
    // 结点关键字个数
    int keyNum;
    // 关键字数组, key[0]不使用
    BKeyType key[MAX_ORDER];
    // 双亲结点指针
    struct BTNode *parent;
    // 孩子结点指针数组
    struct BTNode *ptr[MAX_ORDER];
} BTNode, *BTree;

/**
 * B 树查找结果类型
 */
typedef struct {
    // 指向找到的结点
    BTNode *pt;
    // 在结点中的关键字位置
    int i;
    // 查找成功与否标志, 1成功, 0失败
    bool tag;
} BResult;

/**
 * 链表和链表结点类型
 */
typedef struct BLNode {
    // 数据域
    BTree data;
    // 指针域
    struct BLNode *next;
} BLNode, *BLinkedList;

/**
 * 在树中查找关键字
 * @param t 树
 * @param key 关键字
 * @return 结果
 */
BResult Search_BTree(BTree t, BKeyType key);

/**
 * 在树 t 中插入关键字 k, 返回插入结果
 * @param t 树
 * @param i 索引位置
 * @param k 关键字
 * @param p 结点
 */
void Insert_BTree(BTree *t, int i, BKeyType k, BTNode *p);

/**
 * 删除树 t 中的关键字
 * @param t 树
 * @param k 关键字
 */
void Delete_BTree(BTree t, BKeyType k);

/**
 * 打印 B 树
 * @param t B 树
 */
bool Print_BTree(BTree t);

/**
 * 销毁B树
 * @param t B树
 */
void Destroy_BTree(BTree *t);

#endif //DATA_STRUCTURE_C_BTREE_H




















